﻿package TP3;
import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTree<T extends Comparable<? super T> > 
{
   private RBNode<T> root;  // Racine de l'arbre
   
   enum ChildType{ left, right }
   
   public RedBlackTree()
   { 
      root = null;
   }
   
   public void printFancyTree()
   {
      printFancyTree( root, "", ChildType.right);
   }
   
   private void printFancyTree( RBNode<T> t, String prefix, ChildType myChildType)
   {
      System.out.print( prefix + "|__"); // un | et trois _
      
      if( t != null )
      {
         boolean isLeaf = (t.isNil()) || ( t.leftChild.isNil() && t.rightChild.isNil() );
         
         System.out.println( t );
         String _prefix = prefix;
         
         if( myChildType == ChildType.left )
            _prefix += "|   "; // un | et trois espaces
         else
            _prefix += "   " ; // trois espaces
         
         if( !isLeaf )
         {
            printFancyTree( t.leftChild, _prefix, ChildType.left );
            printFancyTree( t.rightChild, _prefix, ChildType.right );
         }
      }
      else
         System.out.print("null\n");
   }
   
   public T find(int key)
   {
      return find(root, key);
   }
   
   private T find(RBNode<T> current, int key)
   {
      if (current.value == null)
    	  return null;
      int test = current.value.hashCode();
      
      if (test==key)
    	  return current.value;
      else if (test<key)
    	  return find(current.rightChild, key);
      else 
    	  return find(current.leftChild, key);
   }
   
   public void insert(T val)
   {
      insertNode( new RBNode<T>( val ) );
   }
   
   private void insertNode( RBNode<T> newNode )
   { 
      if (root == null)  // Si arbre vide
         root = newNode;
      else
      {
         RBNode<T> position = root; // On se place a la racine
         
         while( true ) // on insere le noeud (ABR standard)
         {
            int newKey = newNode.value.hashCode();
            int posKey = position.value.hashCode();
            
            if ( newKey < posKey ) 
            {
               if ( position.leftChild.isNil() ) 
               {
                  position.leftChild = newNode;
                  newNode.parent = position;
                  break;
               } 
                  else 
                  position = position.leftChild;
            } 
            else if ( newKey > posKey ) 
            {
               if ( position.rightChild.isNil() )
               {
                  position.rightChild = newNode;
                  newNode.parent = position;
                  break;
               }
               else 
                  position = position.rightChild;
            }
            else // pas de doublons
               return;
         }
      }
      
      insertionCases( newNode );
   }

   private void insertionCases( RBNode<T> X )
   {
      
      insertionCase1( X );
   }
   
   private void insertionCase1 ( RBNode<T> X )
   {
      if (X==root)
    	  X.setToBlack();
      else
    	  insertionCase2( X );
   }

   private void insertionCase2( RBNode<T> X )
   {
      if (X.parent.isBlack())
    	  return;
      else
    	  insertionCase3( X );
      
   }

   private void insertionCase3( RBNode<T> X )
   {
      if (X.uncle().isRed())
    	  {
    	  X.uncle().setToBlack();
    	  X.parent.setToBlack();
    	  X.grandParent().setToRed();
    	  
    	  insertionCases( X.grandParent());
    	  
    	  }
      else
    	  insertionCase4( X );
   }

   private void insertionCase4( RBNode<T> X )
   {
      if (X == X.parent.leftChild && X.grandParent().rightChild==X.parent)
      	{
    	  rotateRight( X.parent );
    	  insertionCase5( X.rightChild);
      	}
      else if (X == X.parent.rightChild && X.grandParent().leftChild==X.parent)
      {
    	  rotateLeft( X.parent );
    	  insertionCase5( X.leftChild);
      }
      else
    	  insertionCase5( X );
      
   }

   private void insertionCase5( RBNode<T> X )
   {
      X.grandParent().setToRed();
      X.parent.setToBlack();
      if(X.grandParent().rightChild.rightChild==X)
      {
    	  rotateLeft( X.grandParent() );
      }
      else if(X.grandParent().leftChild.leftChild==X)
      {
    	  rotateRight( X.grandParent() );
      }
      
      return; 
   }
   
   private void rotateLeft( RBNode<T> G )
   {
	   G.rightChild.parent=G.parent;
	   G.rightChild.leftChild.parent=G;
	   G.parent.leftChild=G.rightChild;
	   G.rightChild=G.rightChild.leftChild;
	   G.parent.leftChild.leftChild=G;
	   G.parent=G.parent.leftChild;
   }
   
   private void rotateRight( RBNode<T> G )
   {
	   G.leftChild.parent=G.parent;
	   G.leftChild.rightChild.parent=G;
	   G.parent.rightChild=G.leftChild;
	   G.leftChild=G.leftChild.rightChild;
	   G.parent.rightChild.rightChild=G;
	   G.parent=G.parent.rightChild;
   }

   public void printTreePreOrder()
   {
      if(root == null)
         System.out.println( "Empty tree" );
      else
      {
         System.out.print( "PreOrdre ( ");
         printTreePreOrder( root );
         System.out.println( " )");
      }
      return;
   }
   
   private void printTreePreOrder( RBNode<T> P )
   {
	   if( P.value != null)
	   {
		   if (P!=root)
			   System.out.print(", ");
		   System.out.print("{"+P.toString()+"}");
		   printTreePreOrder(P.leftChild);
		   printTreePreOrder(P.rightChild);
	   }
   }
   
   public void printTreePostOrder()
   {
      if(root == null)
         System.out.println( "Empty tree" );
      else
      {
         System.out.print( "PostOrdre ( ");
         printTreePostOrder( root );
         System.out.println( " )");
      }
      return;
   }
  
   private void printTreePostOrder( RBNode<T> P )
   {
	   if( P.value != null)
	   {
		   printTreePostOrder(P.leftChild);
		   printTreePostOrder(P.rightChild);
		   System.out.print("{"+P.toString()+"}");
		   if (P!=root)
			   System.out.print(", ");
	   }
      
   }
   
   public void printTreeLevelOrder()
   {
      if(root == null)
         System.out.println( "Empty tree" );
      else
      {
         System.out.print( "LevelOrdre ( ");
         
         Queue<RBNode<T>> q = new LinkedList<RBNode<T>>();
         
         q.add(root);
         
         while(!q.isEmpty()){
        	 RBNode<T> node = q.poll();
        	 if (node.value!=null)
        	 {
        		 if (node!=root)
        			   System.out.print(", ");
        		 System.out.print("{"+node.toString()+"}");
        	 }
             if(node.leftChild!= null)
             q.add(node.leftChild);
             if(node.rightChild!= null)
             q.add(node.rightChild);
         }
         
         System.out.println( " )");
      }
      return;
   }
   
   private static class RBNode<T extends Comparable<? super T> > 
   {
      enum RB_COLOR { BLACK, RED }  // Couleur possible
      
      RBNode<T>  parent;      // Noeud parent
      RBNode<T>  leftChild;   // Feuille gauche
      RBNode<T>  rightChild;  // Feuille droite
      RB_COLOR   color;       // Couleur du noeud
      T          value;       // Valeur du noeud
      
      // Constructeur (NIL)   
      RBNode() { setToBlack(); }
      
      // Constructeur (feuille)   
      RBNode(T val)
      {
         setToRed();
         value = val;
         leftChild = new RBNode<T>();
         leftChild.parent = this;
         rightChild = new RBNode<T>();
         rightChild.parent = this;
      }
      
      RBNode<T> grandParent()
      {
         if (parent!=null && parent.parent !=null)
        	 return parent.parent;
         return null;
      }
      
      RBNode<T> uncle()
      {
    	  if (parent!=null && parent.parent !=null)
    	  { 
         	 if (parent.parent.leftChild.value == parent.value) 
         	 {
         		 if (parent.parent.rightChild!=null)
         		 {
         			 return parent.parent.rightChild;
         		 }
         	 }
         	 else
         		if (parent.parent.leftChild!=null)
         		{
         			return parent.parent.leftChild;
         		}
         	}
         return null;
      }
      
      RBNode<T> sibling()
      {
    	  if (parent!=null)
          	 if (parent.leftChild == parent) 
          		 if (parent.rightChild!=null)
          			 return parent.rightChild;
          	 else
          		if (parent.leftChild!=null)
          			return parent.leftChild;
          return null;
      }
      
      public String toString()
      {
         return value + " (" + (color == RB_COLOR.BLACK ? "black" : "red") + ")"; 
      }
      
      boolean isBlack(){ return (color == RB_COLOR.BLACK); }
      boolean isRed(){ return (color == RB_COLOR.RED); }
      boolean isNil(){ return (leftChild == null) && (rightChild == null); }
      
      void setToBlack(){ color = RB_COLOR.BLACK; }
      void setToRed(){ color = RB_COLOR.RED; }
   }
}
